package com.xzz.search;

import java.util.PriorityQueue;

/**
 * @author: hhz
 * @create: 2021-12-29 09:21
 **/
public class FindMedianSortedArrays {

    public static void main(String[] args) {
        int[] num1 = new int[]{3,4};
        int[] num2 = new int[]{1,2};
        System.out.println(findMedianSortedArrays(num1,num2));

        System.out.println(findMedianSortedArrays2(num1, num2));
    }
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        PriorityQueue<Integer> maxQueue = new PriorityQueue<>((o1, o2) -> o2-o1);
        PriorityQueue<Integer> minQueue = new PriorityQueue<>();
        for (int i = 0; i < nums1.length; i++) {
            if(minQueue.size()<=maxQueue.size()){
                maxQueue.offer(nums1[i]);
                minQueue.offer(maxQueue.poll());
            }else {
                minQueue.offer(nums1[i]);
                maxQueue.offer(minQueue.poll());
            }
        }
        for (int i = 0; i < nums2.length; i++) {
            if(minQueue.size()<=maxQueue.size()){
                maxQueue.offer(nums2[i]);
                minQueue.offer(maxQueue.poll());
            }else {
                minQueue.offer(nums2[i]);
                maxQueue.offer(minQueue.poll());
            }
        }
        if((len1+len2)%2 == 0){
            return (maxQueue.peek()+minQueue.peek())/2.0;
        }else {
            return maxQueue.size()>minQueue.size()?maxQueue.peek():minQueue.peek();
        }
    }
    public static double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        PriorityQueue<Integer> minQueue = new PriorityQueue<>();
        int k = (len1+len2) / 2 + 1;
        for (int i : nums1) {
            minQueue.offer(i);
            if(minQueue.size()>k){
                minQueue.poll();
            }
        }
        for (int i : nums2) {
            minQueue.offer(i);
            if(minQueue.size()>k){
                minQueue.poll();
            }
        }
        if((len1+len2)%2 == 0){
            return (minQueue.poll()+minQueue.poll())/2.0;
        }else {
            return minQueue.peek();
        }
    }
}
